package com.leetcode.algorithm.y22.m08.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 654. 最大二叉树
 * 
 * https://leetcode.cn/problems/maximum-binary-tree/
 * 
 * @author jie.deng
 *
 */
class Question0654Solution01 {

	public TreeNode constructMaximumBinaryTree(int[] nums) {
		return constructMaximumBinaryTree(nums, 0, nums.length);
	}

	// [left, rithg)
	private TreeNode constructMaximumBinaryTree(int[] nums, int left, int right) {
		if (left >= right) {
			return null;
		}
		int maxNum = nums[left];
		int maxNumIdx = left;
		for (int i = left + 1; i < right; i++) {
			if (nums[i] > maxNum) {
				maxNum = nums[i];
				maxNumIdx = i;
			}
		}
		TreeNode root = new TreeNode(maxNum);
		root.left = constructMaximumBinaryTree(nums, left, maxNumIdx);
		root.right = constructMaximumBinaryTree(nums, maxNumIdx + 1, right);
		return root;
	}

}